package sort

func main() {
	nums := []int{4, 8, 6, 2, 6, 5}
	//sortedArray := BubbleSort(nums)
	//sortedArray := SelectSort(nums)
	//sortedArray := InsertionSort(nums)
	//sortedArray := MergeSort(nums)
	sortedArray := QuickSort(nums)
	//sortedArray := CountSort(nums)

	for _, item := range sortedArray {
		print(item)
	}
}

// BubbleSort 冒泡排序
func BubbleSort(array []int) []int {
	arrLen := len(array)

	for i := 0; i < arrLen-1; i++ {
		for j := i; j < arrLen-i-1; j++ {
			if array[j] > array[j+1] {
				array[j], array[j+1] = array[j+1], array[j]
			}
		}
	}

	return array
}

// SelectSort  选择排序
func SelectSort(array []int) []int {
	arrLen := len(array)
	for i := 0; i < arrLen-1; i++ {
		minIdx := i
		for j := i + 1; j < arrLen; j++ {
			if array[j] < array[minIdx] {
				minIdx = j
			}
		}
		array[i], array[minIdx] = array[minIdx], array[i]
	}

	return array
}

// InsertionSort 插入排序
func InsertionSort(array []int) []int {
	arrLen := len(array)
	for i := 1; i < arrLen; i++ {
		temp := array[i]
		j := i - 1
		for j >= 0 && array[j] > temp {
			array[j+1] = array[j]
			j--
		}
		array[j+1] = temp
	}
	return array
}

// MergeSort 归并排序
func MergeSort(array []int) []int {
	n := len(array)
	if len(array) <= 1 {
		return array
	}
	mid := n / 2
	leftSide := make([]int, mid)
	rightSide := make([]int, n-mid)
	copy(leftSide, array[:mid])
	copy(rightSide, array[mid:])
	sorted1 := MergeSort(leftSide)
	sorted2 := MergeSort(rightSide)
	res := MergeArrays(sorted1, sorted2)

	return res
}

func MergeArrays(left, right []int) []int {
	n1, n2 := len(left), len(right)
	//result := make([]int, n1+n2)
	//
	//i, j, k := 0, 0, 0
	//
	//// 比较左右数组的元素，并将较小的元素放入结果数组中
	//for i < n1 && j < n2 {
	//	if left[i] <= right[j] {
	//		result[k] = left[i]
	//		i++
	//	} else {
	//		result[k] = right[j]
	//		j++
	//	}
	//	k++
	//}
	//// 将剩余的元素放入结果数组中
	//for i < n1 {
	//	result[k] = left[i]
	//	i++
	//	k++
	//}
	//for j < n2 {
	//	result[k] = right[j]
	//	j++
	//	k++
	//}
	//return result

	result := make([]int, n1+n2) // todo 为什么这里需要先初始化？？？不然就结果不对
	i, j, k := 0, 0, 0
	for i < n1 && j < n2 {
		if left[i] < right[j] {
			result[k] = left[i]
			i++
		} else {
			result[k] = right[j]
			j++
		}
		k++
	}
	for i < n1 {
		result[k] = left[i]
		i++
		k++
	}
	for j < n2 {
		result[k] = right[j]
		j++
		k++
	}
	return result
}

// QuickSort 快速排序
func QuickSort(array []int) []int {
	quickSort(array, 0, len(array)-1)
	return array
}
func quickSort(array []int, low, high int) {
	if low < high {
		pivotIndex := partition3(array, low, high)
		quickSort(array, low, pivotIndex-1)
		quickSort(array, pivotIndex+1, high)
	}
	return
}

func partition3(array []int, low, high int) (pivotIndex int) {
	pivot := array[high]
	i := low - 1

	for j := low; j < high; j++ {
		if array[j] < pivot {
			i++
			array[i], array[j] = array[j], array[i]
		}
	}

	array[i+1], array[high] = array[high], array[i+1]

	return i + 1
}

// CountSort 计数排序
func CountSort(array []int) []int {
	arrLen := len(array)
	if arrLen < 2 {
		return array
	}

	maxNum := array[0]
	for _, arr := range array {
		if arr > maxNum {
			maxNum = arr
		}
	}

	countArray := make([]int, maxNum+1)
	for _, item := range array {
		countArray[item]++
	}

	var resArray []int
	for idx, item := range countArray {
		for i := 0; i < item; i++ {
			resArray = append(resArray, idx)
		}
	}

	return resArray
}
